package zuosheng.Window;

import java.util.LinkedList;

/**
 * @author lj
 * @Description: 生成窗口的最大值或者最小值数组，时间复杂度：O(N)。
 * @date 2020-11-19 12:31
 * @QQ 851477108
 */


public class Window {
    public int[] arr;
    private int left;
    private int right;
    private final LinkedList<Integer> queue;
    public Window(int[] arr){
        this.arr = arr;
        left = 0;
        right = 0;
        queue = new LinkedList<>();
    }

    public Integer getMax(){
        if (queue.isEmpty()){
            return null;
        }
        return arr[queue.peekFirst()];
    }

    // 往滑动窗口加数时对双端队列的操作
    public void addNumToRight(){
        if (right == arr.length){
            // right已经到达最右了，滑动窗口无法再增加数了
            return;
        }

        while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[right]){
            queue.pollLast();
        }

        queue.add(right);
        right++;
    }

    // 移除双端队列最左边的值
    public void removeNumFromLeft(){
        if (left < right){
            // 只有left小于right的时候，才有窗口存在
            if (queue.peekFirst() == left){
                // 要移除的这个数是双端队列的头，则弹出它，表示它已经不在窗口里，失效了
                queue.pollFirst();
            }
        }
        left++;
    }
}
